package leetcode100

// TODO 脑筋急转弯 | 快慢指针plus 【-】 环形链表 II
// TODO https://leetcode.cn/problems/linked-list-cycle-ii/solution/huan-xing-lian-biao-ii-by-leetcode-solution/

func detectCycle(head *ListNode) *ListNode {
    slow, fast := head, head
    for fast != nil {
        slow = slow.Next
        if fast.Next == nil {
            return nil
        }
        fast = fast.Next.Next
        if fast == slow {
            p := head
            for p != slow {     //  a=c+(n-1)(b+c): p 和 slow 一起走, 会在入环点处相遇
                p = p.Next
                slow = slow.Next
            }
            return p
        }
    }
    return nil
}